package meituan.summer11;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

/**
 * @Author Fizz Pu
 * @Date 2021/4/29 下午4:19
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */
public class Main3 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCount = Integer.parseInt(br.readLine().trim());
        for(int count = 0; count < testCount; count++) {

            int len = Integer.parseInt(br.readLine().trim());
            String[] sequence = br.readLine().trim().split(" ");

            int[] data = new int[len];
            int[] minDp = new int[len];
            int[] maxDp = new int[len];


            int sum = 0;
            for (int j = 0; j < len; j++) {
                data[j] = Integer.parseInt(sequence[j]);
                sum += data[j];
            }

            maxDp[0] = data[0];
            minDp[0] = data[0];
            int maxValue = data[0];
            int minValue = data[0];

            for (int i = 1; i < len; i++) {
                maxDp[i] = Math.max(maxDp[i - 1] + data[i], data[i]);
                minDp[i] = Math.min(minDp[i - 1] + data[i], data[i]);
                maxValue = Math.max(maxValue, maxDp[i]);
                minValue = Math.min(minValue, minDp[i]);
            }

            maxValue = Math.max(maxValue, sum - minValue);
            if (maxValue < 0) {
                maxValue = 0;
            }

            System.out.println(maxValue);
        }
    }
    /*public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testNum = scanner.nextInt();
        for(int i = 0; i < testNum; i++){
            int n = scanner.nextInt();
            int[] sequence = new int[n];
            for(int j = 0; j < n; j++){
                sequence[j] = scanner.nextInt();
            }

            int maxValue = Integer.MIN_VALUE;
            int[] dpArray = new int[n];

            for(int j = 0; j < n; j++){
                maxValue = Math.max(maxValue, dp(sequence, j, dpArray));
            }

            if(maxValue < 0){
                maxValue = 0;
            }

            System.out.println(maxValue);
        }
    }

    private static int dp(int[] sequence, int start, int[] dp){
        dp[0] = sequence[start];
        int len = sequence.length;
        int index = start;
        int maxValue = dp[start];
        for(int i = 1; i < len; i++){
            index = (index + 1) % len;
            dp[i] = Math.max(sequence[index], sequence[index] + dp[i - 1]);
            maxValue = Math.max(maxValue, dp[i]);
        }
        return maxValue;
    }*/
}
